\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{float}
\usepackage{subfigure}
\usepackage{amsmath}

\title{双叉搜索树排序的实现}



\author{赖心怡 \\  医学实验班(临床医学八年制) 3210100987}

\begin{document}
\sloppy
\maketitle


\section{项目设计思路}
二叉搜索树排序的基本原理:先构建一棵空树,使用第一个元素作为根节点,如果之后的元素比第一个小,则放到左子树,否则放到右子树,之后按中序遍历.理论上该算法时间复杂度为 $n\log(n)$, 空间复杂度为 $\log(n)$.

在课本提供的 \verb|BinarySearchTree.h| 文件的代码基础上,还需自行实现函数 \verb|void BSTSorting|,功能是将数组排序, \verb|_mode = 0| 时,不乱序；\verb|_mode = 1| 时,先对数组 \verb|_arr| 乱序后再排序.

以下函数通过 Knuth-Durstenfeld Shuffle 算法实现对数组乱序:
\begin{verbatim}
template <typename Comparable>
void Shuffle(std::vector<Comparable> &_arr){
        srand(time(NULL));
        int i = 0;
        for (i = _arr.size() - 1; i > 0; i --){
                int index = rand() % (i + 1);
                std::swap(_arr[i], _arr[index]);
        }
}
\end{verbatim}

以下函数将数组中的元素转换为二叉树结构后输出, 其中 \verb|t.output| 函数实现遍历树中元素并输出到数组中.
\begin{verbatim}
template <typename Comparable>
void BSTSorting(std::vector<Comparable> &_arr, int _mode = 0){
        BinarySearchTree<Comparable> t;
        int i = 0;
        if(!_arr.empty()){
                if(_mode = 1){
                        Shuffle(_arr);
                }
                for (i = 0; i < _arr.size(); i ++){
                        t.insert(_arr[i]);
                }
                //t.output(_arr);
        }
}
\end{verbatim}
\section{测试说明}
测试程序分别测试 \verb|_mode = 0| 的最坏效率(即数组为倒序输入), 和 \verb|_mode = 1| 的平均效率(循环执行程序求平均时间).

以下为测试主程序:
\begin{verbatim}
 // Test program
int main( ){
	vector<int> a;
	int i = 0;
	for ( i = MAXN; i > 0; i --){
		a.push_back(i);
	}
	//the worst case when _mode = 0
        clock_t startTime, endTime;
        startTime = clock();
	BSTSorting(a,0);
	endTime = clock();
	cout << "_mode = 0 : " << (double)(endTime - startTime) * 1000 / CLOCKS_PER_SEC << "ms" << endl;
	//the average case when _mode = 1
	double sumTime = 0;
	for(int n = 1; n <= TESTN; n ++){
		startTime = clock();
	        BSTSorting( a, 1);
		endTime = clock();
		double time =  (double)(endTime - startTime) * 1000 / CLOCKS_PER_SEC;
		cout << "n = " << n << ":" << time << "ms" << endl;
		sumTime = sumTime + time;
	}
	double avgTime = sumTime / TESTN;
	cout << "_mode = 1 : " <<  avgTime << "ms" << endl;
	return 0;
}


\end{verbatim}

测试数组大小 \verb|MAXN = 1000|, 循环次数 \verb|TESTN = 10|,输出结果如下:
\begin{figure}[htbp]
\centering
\begin{subfigure}
	\centering
	\includegraphics{run1.png}
\end{subfigure}
\centering
\begin{subfigure}
        \centering
        \includegraphics{run2.png}
\end{subfigure}

\end{figure}

内存泄漏检查结果如下,说明无内存泄漏:
\begin{verbatim}
==2593== HEAP SUMMARY:
==2593==     in use at exit: 0 bytes in 0 blocks
==2593==   total heap usage: 11,013 allocs, 11,013 frees, 345,916 bytes allocated
==2593==
==2593== All heap blocks were freed -- no leaks are possible
==2593==
==2593== For counts of detected and suppressed errors, rerun with: -v
==2593== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
\end{verbatim}
\end{document}
